0% completed
Problem Statement
Given an array arr containing strings, return the maximum length of the string that can be formed by the concatenations of the subsequence of arr, having unique characters.
A subsequence is an array that can be formed from arr by deleting 0 or more elements without changing the order of the remaining elements.
Examples
-
Example 1:
- Input: ["ab", "cd", "e"]
- Expected Output: 5
- Justification: Concatenating "ab", "cd", and "e" forms "abcde" which has all unique characters and is of maximum length 5.
-
Example 2:
- Input: ["a", "abc", "d", "de", "def"]
- xpected Output: 6
- Justification: Concatenating "abc", and "def" forms "abcdef" which has all unique characters and is of maximum length 6.
-
Example 3:
- Input: ["xyz", "y", "z"]
- Expected Output: 3
- Justification: We can choose only "xyz" string. Hence, the maximum length is 3.
Solution
The approach to solving the maximum length of a concatenated string with unique characters from a list involves an iterative method that expands on unique combinations progressively. Starting with an empty string, the algorithm combines each input string to previously validated unique sequences, updating a running maximum length whenever a longer unique combination is discovered.
This strategy ensures all possible combinations are explored efficiently, leveraging the simplicity of iterative expansion and the effectiveness of uniqueness checks. By focusing on incremental growth and meticulous validation, the method efficiently navigates through the potential combinations, identifying the optimal sequence length with precision and minimal computational overhead.
Step-by-step Algorithm
- Initialize a list
resultscontaining one empty string. This list will store all unique character combinations found so far, starting with a possibility to build from an empty combination. - Initialize a variable
bestto 0, which will keep track of the maximum length of any unique character string formed throughout the process. - Iterate over each word in the given list
arr.- For each
wordinarr, iterate over the combinations already inresults(only those that existed before this iteration started, tracked byresultsLen).- Concatenate the current
wordwith each existing combination (referred to asexistingCombination). - Check if the new combination
newRes(the result of concatenation) has all unique characters by calling theisUniquemethod.- If
newResis unique, add it toresultsfor consideration in future combinations. - Update
bestto be the maximum of its current value or the length ofnewRes.
- If
- Concatenate the current
- For each
- After exploring all words and their possible unique combinations, return
bestas the solution, representing the maximum length of a concatenated string with all unique characters.
Algorithm Walkthrough
Let's consider the Input ["a", "abc", "d", "de", "def"]
- Initialize
resultswith an empty string:results = [""] - Initialize
best = 0 - Start iterating over the array:
-
First iteration with "a":
resultscontains[""].- Concatenate "a" with "", resulting in "a".
- Check uniqueness of "a", which is true.
- Add "a" to
results, nowresults = ["", "a"]. - Update
bestto 1.
-
Second iteration with "abc":
- Now,
resultscontains["", "a"]. - Concatenate "abc" with "", resulting in "abc". Add "abc" to
results, and updatebestto 3. - Concatenate "abc" with "a", but "aabc" is not unique, so skip adding.
resultsis now["", "a", "abc"].
- Now,
-
Third iteration with "d":
resultscontains["", "a", "abc"].- Concatenate "d" with each combination in
results, resulting in valid unique strings "d", "ad", "abcd". - Add all valid combinations to
results, nowresults = ["", "a", "abc", "d", "ad", "abcd"]. - Update
bestto 4 (length of "abcd"). Certainly, let's correct the walkthrough for the 4th and 5th iterations, focusing on accurately reflecting how the algorithm builds up to the correct maximum length with the input["a", "abc", "d", "de", "def"].
-
Fourth iteration with "de":
- At this point,
resultscontains["", "a", "abc", "d", "ad", "abcd"]. - Concatenate "de" with each valid combination from the previous step:
- Concatenating "de" with "", "a", and "d" results in "de", "ade", and "dde", respectively. However, "dde" is not unique and is not added.
- Concatenating "de" with "abc" results in "abcde", which is unique and added to
results. - "de" with "ad" forms "adde", which is not unique and thus not added.
- "de" with "abcd" would repeat characters and is thus not considered a valid new addition.
- After this iteration, valid new combinations like "de", "ade", and "abcde" are added. The most significant update here is "abcde", which increases
bestto 5. resultsnow includes these new unique combinations, making it larger, but for brevity, the key addition to note is"abcde".- Final
resultsarray at this point: ["", "a", "abc", "d", "ad", "abcd", "de", "ade", "abcde", ...]
- At this point,
-
Fifth iteration with "def":
- Starting with the updated
resultsfrom the last step, which now includes "abcde" among others. - Concatenate "def" with each valid combination from
results: - Adding "def" to "", "a", "d", "ad", and notably "abcde" among others.
- Most combinations either remain unchanged in terms of their contribution to
bestor are invalid due to repeated characters. - However, adding "def" to "abc" results in "abcdef", which is unique and thus a crucial addition.
- The addition of "abcdef" is significant as it updates
bestto 6, which represents the longest unique combination possible from the given input.
- Starting with the updated
-
Final
resultsarray at this point: ["", "a", "abc", "d", "ad", "abcd", "de", "ade", "abcde", "def", "adef", "abcdef", ...]
-
Code
Complexity Analysis
-
Time Complexity: The worst-case time complexity is
, where N is the number of strings in the input list and K is the maximum length of a string. This is because, in the worst case, each string can either be included or excluded from each combination, leading to combinations. For each combination, checking uniqueness and concatenating strings can take up to time. -
Space Complexity: The space complexity is
, primarily due to storing all possible combinations of strings. In the worst case, this could include all combinations, each of up to K characters in length.
On this page
Problem Statement
Examples
Solution
Step-by-step Algorithm
Algorithm Walkthrough
Code
Complexity Analysis